// 泰波那契序列 Tn 定义如下： 
// T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
// 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。


// 备忘录形式的递归去除重叠子问题


/**
 * @param {number} n
 * @return {number}
 */
var tribonacci = function (n) {
    // memo备忘录，将计算过的f(n)数值存在数组的第n项中
    let memo = [];
    memo[0] = 0;
    function recursion(memo, n) {
        if (n === 0) return 0;
        if (n === 1 || n === 2) return 1;
        // 如果存在，将不再计算
        if (memo[n]) { return memo[n] }
        memo[n] = recursion(memo, n - 1) + recursion(memo, n - 2) + recursion(memo, n - 3);
        return memo[n];
    }
    return recursion(memo, n);
};



// dp的迭代形式，并进行状态压缩。将memo（dptable）压缩为两个变量
/**
 * @param {number} n
 * @return {number}
 */
var tribonacci_dp = function (n) {
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;
    // 初始化两个变量
    let
        before = 0
        pre = 1,
        cur = 1,
        i = 3;
    for (; i <= n; i++) {
        let sum = pre + cur + before;
        before = pre;
        pre = cur;
        cur = sum;
    };
    return cur
};